package algorithms.sorts;

import algorithms.Utils;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        // int[] arr = {1000, -100, -6, 300, -90,1, 8, 101, 13, 4};
        int[] arr = Utils.randomArray(3001000);
        System.out.println(Utils.isAscend(arr));
        System.out.println("           start:" + System.currentTimeMillis());
        mergeSort(arr);
        System.out.println("       mergeSort:" + System.currentTimeMillis());
        mergeSortDown2Up(arr);
        System.out.println("mergeSortDown2Up:" + System.currentTimeMillis());
        System.out.println(Utils.isAscend(arr));
        //System.out.println(Arrays.toString(arr));

    }

    private static void mergeSort(int arr[]) {
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int arr[], int from, int to) {
        if (from == to) {
            return;
        }

        int mid = (from + to) >> 1;
        mergeSort(arr, from, mid);
        mergeSort(arr, mid + 1, to);

        //insertMerge(arr, from, mid, to);
        extraSpaceMerge(arr, from, mid, to);
    }


    /**
     * 插入排序方式合并，大数据量移动数据次数多，效率底
     *
     * @param arr
     * @param from
     * @param mid
     * @param to
     */
    private static void insertMerge(int[] arr, int from, int mid, int to) {
        for (int i = mid + 1; i <= to; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= from && (temp < arr[j])) {
                arr[j + 1] = arr[j--];

            }
            if (j == i - 1) break;//说明插入的值比前面所有值都大，而后面的值必然大于等于插入的值，此时form->to有序
            arr[j + 1] = temp;
        }
    }

    /**
     * 辅助空间合并，速度快，空间换时间
     *
     * @param arr
     * @param from
     * @param mid
     * @param to
     */
    private static void extraSpaceMerge(int[] arr, int from, int mid, int to) {
        int[] temArr = new int[to - from + 1];
        int i = from;
        int j = mid + 1;
        int k = 0;
        int ei, ej;
        while (true) {
            if (i > mid) {
                System.arraycopy(arr, j, temArr, k, temArr.length - k);
                break;
            } else {
                if (j > to) {
                    System.arraycopy(arr, i, temArr, k, temArr.length - k);
                    break;
                } else {
                    ei = arr[i];
                    ej = arr[j];
                    if (ei < ej) {
                        temArr[k++] = ei;
                        i++;
                    } else {
                        temArr[k++] = ej;
                        j++;
                    }
                }
            }
        }
        System.arraycopy(temArr, 0, arr, from, temArr.length);
    }


    /**
     * 自下而上，无递归
     *
     * @param arr
     */
    private static void mergeSortDown2Up(int[] arr) {
        int length = arr.length;
        int endIndex = arr.length - 1;
        for (int gap = 1; gap < length; gap *= 2) {
            for (int i = 0; i < length; i += 2 * gap) {
                int m = i + gap - 1;
                m = m > endIndex ? endIndex : m;
                int h = m + gap;
                h = h > endIndex ? endIndex : h;
                //System.out.println("gap:" + gap + ",merge:" + i + "," + m + "," + h);
                extraSpaceMerge(arr, i, m, h);
                //insertMerge(arr, i, m, h);
            }
            //System.out.println(Arrays.toString(arr));
            //System.out.println("===========================");
        }
    }
}
